package de.szut.tree;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;

/**
 * Traversal orders for binary search tree traversal
 * @author Marc Huisinga
 *
 */
public enum Traversal {
	
	/**
	 * Traverses the tree in pre order.
	 * Recursive steps:
	 *  - Visit the current node
	 *  - Traverse the left subtree
	 *  - Traverse the right subtree
	 */
	PRE_ORDER {
		@Override
		<K, V> Generator<Node<K, V>> traverse(Node<K, V> start) {
			return () -> {
				return new Iterator<Node<K, V>>() {

					Stack<Node<K, V>> rightChildrenStack = new Stack<>();
					Node<K, V> currentNode = start;

					@Override
					public boolean hasNext() {
						return !(rightChildrenStack.empty() && currentNode == null);
					}

					@Override
					public Node<K, V> next() {
						if (!hasNext()) {
							throw new NoSuchElementException(NO_ELEMENTS_LEFT);
						}
						while (true) {
							if (currentNode != null) {
								if (currentNode.getRightChild() != null) {
									rightChildrenStack.push(currentNode.getRightChild());
								}
								Node<K, V> visitedNode = currentNode;
								currentNode = currentNode.getLeftChild();
								return visitedNode;
							} else {
								currentNode = rightChildrenStack.pop();
							}
						}
					}

				};
			};
		}
	},
	
	/**
	 * Traverses the tree in ascending order.
	 * Recursive steps:
	 *  - Traverse the left subtree
	 *  - Visit the current node
	 *  - Traverse the right subtree
	 */
	ASCENDING {
		@Override
		<K, V> Generator<Node<K, V>> traverse(Node<K, V> start) {
			return () -> {
				return new Iterator<Node<K, V>>() {

					Stack<Node<K, V>> parentStack = new Stack<>();
					Node<K, V> currentNode = start;

					@Override
					public boolean hasNext() {
						return !(parentStack.empty() && currentNode == null);
					}

					@Override
					public Node<K, V> next() {
						if (!hasNext()) {
							throw new NoSuchElementException(NO_ELEMENTS_LEFT);
						}
						while (true) {
							if (currentNode != null) {
								parentStack.push(currentNode);
								currentNode = currentNode.getLeftChild();
							} else {
								currentNode = parentStack.pop();
								Node<K, V> visitedNode = currentNode;
								currentNode = currentNode.getRightChild();
								return visitedNode;
							}
						}
					}

				};
			};
		}
	},
	
	/**
	 * Traverses the tree in descending order.
	 * Recursive steps:
	 *  - Traverse the right subtree
	 *  - Visit the current node
	 *  - Traverse the left subtree
	 */
	DESCENDING {
		@Override
		<K, V> Generator<Node<K, V>> traverse(Node<K, V> start) {
			return () -> {
				return new Iterator<Node<K, V>>() {

					Stack<Node<K, V>> parentStack = new Stack<>();
					Node<K, V> currentNode = start;

					@Override
					public boolean hasNext() {
						return !(parentStack.empty() && currentNode == null);
					}

					@Override
					public Node<K, V> next() {
						if (!hasNext()) {
							throw new NoSuchElementException(NO_ELEMENTS_LEFT);
						}
						while (true) {
							if (currentNode != null) {
								parentStack.push(currentNode);
								currentNode = currentNode.getRightChild();
							} else {
								currentNode = parentStack.pop();
								Node<K, V> visitedNode = currentNode;
								currentNode = currentNode.getLeftChild();
								return visitedNode;
							}
						}
					}

				};
			};
		}
	},
	
	/**
	 * Traverses the tree in post order.
	 * Recursive steps:
	 *  - Traverse the left subtree
	 *  - Traverse the right subtree
	 *  - Visit the current node
	 */
	POST_ORDER {
		@Override
		<K, V> Generator<Node<K, V>> traverse(Node<K, V> start) {
			return () -> {
				return new Iterator<Node<K, V>>() {

					Stack<Node<K, V>> parentStack = new Stack<>();
					Node<K, V> currentNode = start;
					Node<K, V> lastVisitedNode = null;

					@Override
					public boolean hasNext() {
						return !(parentStack.empty() && currentNode == null);
					}

					@Override
					public Node<K, V> next() {
						if (!hasNext()) {
							throw new NoSuchElementException(NO_ELEMENTS_LEFT);
						}
						while (true) {
							if (currentNode != null) {
								parentStack.push(currentNode);
								currentNode = currentNode.getLeftChild();
							} else {
								Node<K, V> peekNode = parentStack.peek();
								Node<K, V> rightPeekNodeChild = peekNode.getRightChild();
								if (rightPeekNodeChild != null && lastVisitedNode != rightPeekNodeChild) {
									currentNode = rightPeekNodeChild;
								} else {
									lastVisitedNode = parentStack.pop();
									return peekNode;
								}
							}
						}
					}

				};
			};
		}
	},
	
	/**
	 * Traverses a tree in breadth-first order.
	 * Visits every node from left to right in each line from top to bottom.
	 */
	BREADTH_FIRST {
		@Override
		<K, V> Generator<Node<K, V>> traverse(Node<K, V> start) {
			if (start == null) {
				return Generator.empty();
			}
			return () -> {
				return new Iterator<Node<K, V>>() {

					Queue<Node<K, V>> lineQueue = new LinkedList<>(Arrays.asList(start));
					Node<K, V> currentNode = start;
					
					@Override
					public boolean hasNext() {
						return !lineQueue.isEmpty();
					}

					@Override
					public Node<K, V> next() {
						if (!hasNext()) {
							throw new NoSuchElementException(NO_ELEMENTS_LEFT);
						}
						currentNode = lineQueue.remove();
						Node<K, V> leftChild = currentNode.getLeftChild();
						if (leftChild != null) {
							lineQueue.add(leftChild);
						}
						Node<K, V> rightChild = currentNode.getRightChild();
						if (currentNode.getRightChild() != null) {
							lineQueue.add(rightChild);
						}
						return currentNode;
					}
					
				};
			};
		}
	};
	
	/**
	 * Traverses the tree until no more elements are left to traverse.
	 * @param start - node to start traversing at, usually the root
	 * @return generator for lazy evaluation
	 */
	abstract <K, V> Generator<Node<K, V>> traverse(Node<K, V> start);
	
	private static final String NO_ELEMENTS_LEFT = "No tree elements left to traverse.";
	
}
